package minimalshift;

import org.jgrapht.Graph;

import java.util.*;

/**
 * Komentar od Michal Trnka - tuhle tridu jsem stahnul a upravil z
 * https://bitbucket.org/sorend/jgrapht-sna/src/0044c67792aa/src/main/java/dk/aaue/sna/alg/hierarchy/BellmanFordShortestPathWithNegativeCycleDetector.java
 *
 * A slightly modified version of the bellman ford algorithm, implemented to
 * detect negative cycles, by adding an additional step. (Note, this is
 * implemented from scratch, not by modifying JGraphT's BellmanFordShortestPath)
 * For information on the algorithm, see
 * {@linkplain <a href="http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm">Bellman-Ford on Wikipedia</a>}.
 *
 * @author Soren A. Davidsen <soren@tanesha.net>
 */
public class NegativeCostCycleDetector {

	private Graph<Integer, GraphEdge> graph;
	private int source;
	private Map<Integer, Double> distance = null;
	private Map<Integer, Integer> predecessor = null;
	private boolean negativeCycle = false;
	private List<GraphEdge> negativeCycleVertices = null;

	/**
	 * Constructor.
	 *
	 * @param graph The graph
	 * @param source The source
	 */
	public NegativeCostCycleDetector(Graph<Integer, GraphEdge> graph, int source) {
		this.graph = graph;
		this.source = source;
	}

	protected void lazyCalculate() {

		if (distance != null) {
			return;
		}

		distance = new HashMap<>();
		predecessor = new HashMap<>();

		// initialize
		for (int v : graph.vertexSet()) {
			if (v == source) {
				distance.put(v, 0.0);
			} else {
				distance.put(v, Double.POSITIVE_INFINITY);
			}
		}

		// relax n-1 times.
		int n = graph.vertexSet().size();
		for (int i = 0; i < n - 1; i++) {
			for (GraphEdge e : graph.edgeSet()) {
				int u = graph.getEdgeSource(e);
				int v = graph.getEdgeTarget(e);
				double weight = e.getCost();
				if (distance.get(u) + weight < distance.get(v)) {
					distance.put(v, distance.get(u) + weight);
					if (predecessor != null) {
						predecessor.put(v, u);
					}
				}
			}
		}


		// check Vth time if we can relax any more (=negative cycle detected)
		for (GraphEdge e : graph.edgeSet()) {
			int u = graph.getEdgeSource(e);
			int v = graph.getEdgeTarget(e);
			double weight = e.getCost();
			if (distance.get(u) + weight < distance.get(v)) {
				negativeCycle = true;
				negativeCycleVertices = constructPath(u);
				break;
			}
		}
	}

	private List<GraphEdge> constructPath(int start) {

		// System.out.println("Constructing path: start=" + start + ", end=" + end);
		List<GraphEdge> R = new ArrayList<>();
		Set<Integer> visited = new HashSet<>();
		
		int cur = start;
		while (true) {
			visited.add(cur);
			R.add(graph.getEdge(predecessor.get(cur), cur));

			cur = predecessor.get(cur);
			if (cur == start) {
				break;
			}
			if(visited.contains(cur)){
				return constructPath(cur);
			}
		}

		return R;
	}

	/**
	 * Returns the cost of the path from source to sink (destination).
	 *
	 * @param sink The destination
	 * @return the cost
	 */
	public double getCost(int sink) {
		lazyCalculate();
		return distance.get(sink);
	}

	/**
	 * Evaluates if the graph contains a negative cycle.
	 *
	 * @return
	 */
	public boolean hasNegativeCycle() {
		lazyCalculate();
		return negativeCycle;
	}

	/**
	 * Returns the edges of the negative cycle (use
	 * {@link dk.aaue.sna.alg.hierarchy.BellmanFordShortestPathWithNegativeCycleDetector#hasNegativeCycle()}
	 * first.
	 *
	 * @return
	 */
	public List<GraphEdge> getNegativeCycleVertices() {
		return negativeCycleVertices;
	}
}